<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>KMP</title>
  </head>
  <body>
    <script>
      //   function find(source, pattern) {
      //     for (var i = 0; i < source.length; i++) {
      //       let isMatch = true;
      //       for (var j = 0; j < pattern.length; j++) {
      //         if (source[i + j] !== pattern[j]) {
      //           isMatch = false;
      //           break;
      //         }
      //       }
      //       if (isMatch) {
      //         return true;
      //       }
      //     }
      //     return false;
      //   }
      function findByKMP(source, pattern) {
        let table = new Array(pattern.length).fill(0);
        let k = 0;
        for (let j = 1; j < pattern.length; j++) {
          if (pattern[j] === pattern[k]) {
            k++;
          } else {
            k = 0;
          }
          table[j] = k;
        }
        let j = 0;
        for (let i = 0; i < source.length; i++) {
          console.log(source[i], pattern[j]);
          if (source[i] === pattern[j]) {
            j++;
          } else {
            // j = 0;
            // j = table[j-1];
            // if (source[i] === pattern[j]) {
            //   j++;
            // }
            while (source[i] !== pattern[j] && j > 0) {
              j = table[j - 1];
            }
            if (source[i] === pattern[j]) {
              j++;
            } else {
              j = 0;
            }
          }

          if (j === pattern.length) return true;
        }
        return false;
      }
      // console.log(findByKMP("abxxyz", "xy"));
      console.log(findByKMP("abcabcabx", "abcabx"));
    </script>
  </body>
</html>
